It is often useful to measure the latency between two nodes in a network. However, as the size of a network grows, it is not always practical to perform point to point latency measurements between every given node in a network.
Several schemes have been proposed to estimate Internet distances (or latency). For example, Internet Distance Maps (IDMaps) and Dynamic Distance Maps (DDM) place tracers at key locations in the Internet. These tracers measure the latency between themselves and advertise the measured information to clients. The distance between two clients A and B is estimated as the sum of the distance between A and its closest tracer A′, the distance between B and its closest tracer B′, and the distance between tracers A′ and B′.
M-Coop utilizes a network of nodes linked in a way that mimics the autonomous system (AS) graph extracted from BGP reports. Each node measures distances to a small set of peers. When an estimate between two IP addresses is required, several measurements are composed recursively to provide an estimate. King is similar in spirit to IDMaps and M-coop. It takes advantage of existing DNS architecture and uses the DNS servers as measurement nodes.
A number of schemes have proposed landmark techniques for network distance estimation. Landmark clustering techniques use a node's distance to a common set of landmark nodes to estimate the node's physical position. The intuition behind these techniques is that if two nodes have similar latencies to the land mark nodes, they are likely to be close to each other.
In landmark ordering, a node measures its round-trip time (RTT) to a set of landmarks and sorts the landmark nodes in the order of increasing round-trip time. Therefore, each node has an associated order of landmarks. Nodes with the same or similar landmark order(s) are considered to be close to each other. However, the technique cannot differentiate between nodes with the same landmark orders.
Despite numerous variations, previously described landmark techniques all share one major problem. They cause false clustering where nodes that have similar landmark vectors but are far away in network distance are clustered near each other.
While it can be seen that a number of latency estimation schemes have been proposed, alternative systems and methods for providing latency estimates are desirable.